'

Using the cases of the Master theorem below.

1. If f(n) = O(nd) where d < logba, then f(n) grows polynomially slower than nlogba therefore T(n) = O(nlogba).

2. If f(n) = O(nd) where d > logba, then f(n) grows polynomially faster than nlogba therefore T(n) = O(nd).

3. If f(n) = O(ndlogkn) where d = logba, then T(n) = O(ndlogk+1n).

Consider the following recurrence relations. Apply Master Theorem to express the time complexity in Big-O expression. Show all your work.

1.T(n)=T(n/2)+ O(n)

2.T(n)= 2T(n/2)+ 2nlogn

3.T(n)=T(n/2)+ 45

4.T(n)=5T(n/5)+ O(1)